package com.julius.design.suanfa.search;

/**
 * @author Julius Zhou
 * @title: design
 * @package com.julius.design.suanfa.search
 * @date 2021-10-23 11:02
 * @description: 在二维数组中进行二分查找
 * https://leetcode-cn.com/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof
 */
public class Find2DArray {


    /*
[
  [1,   4,  7, 11, 15],
  [2,   5,  8, 12, 19],
  [3,   6,  9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
]

[[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]]
     */

    public static void main(String[] args) {
        int[][] ma = new int[0][0];
        System.out.println(findNumberIn2DArray(ma,20));
    }


    public static boolean findNumberIn2DArray(int[][] matrix, int target) {
        /*
            第一种方案: 双层遍历,那么时间复杂度为O(N^2),不可取
            第二种方案: 二维数组的二分查找
        */
        //行数
        int r = matrix.length;

        //列数
        int l = 0;
        if (r > 0) {
            l = matrix[0].length;
        }

        for (int i = 0; i < r; i++) {
            int leftL = 0,rightL = l-1;
            while (leftL <=rightL){
                //列的二分查找
                int midL = (leftL+rightL)/2;
                if(matrix[i][midL] == target){
                    return true;
                }
                if (matrix[i][midL] > target){
                    rightL = midL - 1;
                }else{
                    leftL = midL + 1;
                }
            }
        }
        return false;
    }
}
